class Solution(object):
    def minimalKSum(self, nums, k):
        nums = list(set(nums))
        nums.sort()
        n = len(nums)
        ans = 0
        nums.sort()
        index = 0
        while index < n and k > 0:
            if index == 0:
                if nums[index] > k:
                    ans += (1 + k) * k // 2
                    k = 0
                else:
                    k -= (nums[index] - 1)
                    ans += nums[index] * (nums[index] - 1) // 2
            else:
                if nums[index] - nums[index - 1] > k:
                    ans += (nums[index - 1] + 1 + nums[index - 1] + k) * k // 2
                    k = 0
                else:
                    k -= (nums[index] - nums[index - 1] - 1)
                    ans += (nums[index - 1] + 1 + nums[index] - 1) * (nums[index] - nums[index - 1] - 1) // 2
            index += 1
        if k > 0:
            ans += (nums[-1] + 1 + nums[-1] + k) * k // 2
        return ans